package data_structure;

public class leetcode_0106 {

        public TreeNode buildTree(int[] inorder, int[] postorder) {
            return buildTree1(inorder, 0, inorder.length, postorder, 0, postorder.length);
        }
        public TreeNode buildTree1(int[] inorder, int inLeft, int inRight,
                                   int[] postorder, int postLeft, int postRight) {
            // 没有元素了
            if (inRight - inLeft < 1) {
                return null;
            }
            // 只有一个元素了
            if (inRight - inLeft == 1) {
                return new TreeNode(inorder[inLeft]);
            }
            // 后序数组postorder里最后一个即为根结点
            int rootVal = postorder[postRight - 1];
            TreeNode root = new TreeNode(rootVal);
            int rootIndex = 0;
            // 根据根结点的值找到该值在中序数组inorder里的位置
            for (int i = inLeft; i < inRight; i++) {
                if (inorder[i] == rootVal) {
                    rootIndex = i;
                    break;
                }
            }
            // 根据rootIndex划分左右子树
            root.left = buildTree1(inorder, inLeft, rootIndex,
                    postorder, postLeft, postLeft + (rootIndex - inLeft));
            root.right = buildTree1(inorder, rootIndex + 1, inRight,
                    postorder, postLeft + (rootIndex - inLeft), postRight - 1);
            return root;
        }

}
